{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Fair Candy Swap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: fairCandySwap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #公平的糖果交换"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>爱丽丝和鲍勃拥有不同总数量的糖果。给你两个数组 <code>aliceSizes</code> 和 <code>bobSizes</code> ，<code>aliceSizes[i]</code> 是爱丽丝拥有的第 <code>i</code> 盒糖果中的糖果数量，<code>bobSizes[j]</code> 是鲍勃拥有的第 <code>j</code> 盒糖果中的糖果数量。</p>\n",
    "\n",
    "<p>两人想要互相交换一盒糖果，这样在交换之后，他们就可以拥有相同总数量的糖果。一个人拥有的糖果总数量是他们每盒糖果数量的总和。</p>\n",
    "\n",
    "<p>返回一个整数数组 <code>answer</code>，其中 <code>answer[0]</code> 是爱丽丝必须交换的糖果盒中的糖果的数目，<code>answer[1]</code> 是鲍勃必须交换的糖果盒中的糖果的数目。如果存在多个答案，你可以返回其中 <strong>任何一个</strong> 。题目测试用例保证存在与输入对应的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>aliceSizes = [1,1], bobSizes = [2,2]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>aliceSizes = [1,2], bobSizes = [2,3]\n",
    "<strong>输出：</strong>[1,2]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>aliceSizes = [2], bobSizes = [1,3]\n",
    "<strong>输出：</strong>[2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>aliceSizes = [1,2,5], bobSizes = [2,4]\n",
    "<strong>输出：</strong>[5,4]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= aliceSizes.length, bobSizes.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= aliceSizes[i], bobSizes[j] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>爱丽丝和鲍勃的糖果总数量不同。</li>\n",
    "\t<li>题目数据保证对于给定的输入至少存在一个有效答案。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [fair-candy-swap](https://leetcode.cn/problems/fair-candy-swap/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [fair-candy-swap](https://leetcode.cn/problems/fair-candy-swap/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1]\\n[2,2]', '[1,2]\\n[2,3]', '[2]\\n[1,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sum_alice,sum_bob = 0,0\n",
    "        for a in aliceSizes:\n",
    "            sum_alice+= a\n",
    "        for b in bobSizes:\n",
    "            sum_bob+=b\n",
    "        sum = sum_alice+sum_bob\n",
    "        aim = sum/2\n",
    "        key = sum_alice-aim\n",
    "        for x in aliceSizes:\n",
    "            if (x - key)in bobSizes :\n",
    "                return [x,x-key]\n",
    "        return []\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        aliceSizes.sort()\n",
    "        bobSizes.sort()\n",
    "        difference = (sum(aliceSizes) - sum(bobSizes)) // 2\n",
    "        i,j = 0,0\n",
    "        while i < len(aliceSizes) and j < len(bobSizes):\n",
    "            d = aliceSizes[i] - bobSizes[j]\n",
    "            if d < difference:\n",
    "                i += 1\n",
    "                while aliceSizes[i] == aliceSizes[i - 1]:\n",
    "                    i += 1\n",
    "            elif d > difference:\n",
    "                j += 1\n",
    "                while bobSizes[j] == bobSizes[j - 1]:\n",
    "                    j += 1\n",
    "            else:\n",
    "                return [aliceSizes[i],bobSizes[j]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        a=sum(aliceSizes)\n",
    "        b=sum(bobSizes)\n",
    "        c=(a+b)//2\n",
    "        for i in aliceSizes:\n",
    "            if i-(a-c) in bobSizes:\n",
    "                return [i,i+c-a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        def binarySearch(i, j, target, nums):\n",
    "            while j - i > 3:\n",
    "                mid = (i + j) >> 1\n",
    "                if nums[mid] == target: return nums[mid]\n",
    "                elif nums[mid] > target: j = mid -1 \n",
    "                else: i = mid + 1\n",
    "            if target == 66: print(i, j)\n",
    "            for i in range(i, j+1):\n",
    "                if nums[i] == target:\n",
    "                    return nums[i]\n",
    "            return -1\n",
    "\n",
    "        alice = sum(aliceSizes)\n",
    "        bob = sum(bobSizes)\n",
    "        total = alice + bob\n",
    "        aliceSizes.sort()\n",
    "        bobSizes.sort()\n",
    "        res = []\n",
    "        for i in range(len(aliceSizes)-1, -1, -1):\n",
    "            target = total // 2 - alice + aliceSizes[i]\n",
    "            bob_give = binarySearch(0, len(bobSizes)-1, target, bobSizes)\n",
    "            if bob_give != -1:\n",
    "                res.append(aliceSizes[i])\n",
    "                res.append(bob_give)\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        #方法一：排序，返回liceSizes[i]-bobSizes[j]等于sum(aliceSizes)-sum(bobSizes)的一半的[liceSizes[i],bobSizes[j]]\n",
    "        total_a,total_b = sum(aliceSizes),sum(bobSizes)\n",
    "        dif = total_a - total_b\n",
    "        aliceSizes.sort()\n",
    "        bobSizes.sort()\n",
    "        i,j = 0,0\n",
    "        while i<len(aliceSizes) and j<len(bobSizes):\n",
    "            if aliceSizes[i]-bobSizes[j] == dif//2:\n",
    "                return [aliceSizes[i],bobSizes[j]]\n",
    "            elif aliceSizes[i]-bobSizes[j] < dif//2:\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        a=sum(aliceSizes)\n",
    "        b=sum(bobSizes)\n",
    "        c=int((a-b)/2)\n",
    "        for i in aliceSizes:\n",
    "            if i-c in bobSizes:\n",
    "                return [i,i-c] \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        aliceSizes = sorted(aliceSizes)\n",
    "        m, n, d = len(aliceSizes), len(bobSizes), sum(aliceSizes) - sum(bobSizes)\n",
    "        res = []\n",
    "        for b in bobSizes:\n",
    "            l, r = 0, m - 1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if (aliceSizes[mid] - b) >= d // 2:\n",
    "                    r = mid\n",
    "                else: l = mid + 1\n",
    "            if aliceSizes[l] - b == d // 2:\n",
    "                res = [aliceSizes[l], b]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        aliceSum = 0\n",
    "        bobSum = 0\n",
    "        for i in aliceSizes:\n",
    "            aliceSum +=i\n",
    "        for i in bobSizes:\n",
    "            bobSum +=i\n",
    "\n",
    "        sum = aliceSum + bobSum\n",
    "        avg = sum//2\n",
    "\n",
    "        for i in aliceSizes:\n",
    "            if aliceSum - i >= avg:\n",
    "                continue\n",
    "            else:\n",
    "                compare = avg - (aliceSum - i )\n",
    "                if compare in bobSizes:\n",
    "                    return [i,compare]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        aliceSum = sum(aliceSizes)\n",
    "        bobSum = sum(bobSizes)\n",
    "        avg = (aliceSum + bobSum)//2\n",
    "\n",
    "        for i in aliceSizes:\n",
    "            if aliceSum - i >= avg:\n",
    "                continue\n",
    "            else:\n",
    "                compare = avg - (aliceSum - i )\n",
    "                if compare in bobSizes:\n",
    "                    return [i,compare]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        for x in aliceSizes:\n",
    "            if x + (sum(bobSizes) - sum(aliceSizes)) / 2 in bobSizes:\n",
    "                return [x, x + (sum(bobSizes) - sum(aliceSizes)) / 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\r\n",
    "        average = int((sum(aliceSizes)+sum(bobSizes))/2)\r\n",
    "        ans = list()\r\n",
    "        for i in aliceSizes:\r\n",
    "            if average - sum(aliceSizes) + i in bobSizes:\r\n",
    "                ans.append(i)\r\n",
    "                ans.append(sum(bobSizes)+i-average)\r\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sub = (sum(aliceSizes) - sum(bobSizes)) // 2\n",
    "        for i in aliceSizes:\n",
    "            if i - sub in bobSizes:\n",
    "                return [i, i - sub]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        tmp = (sum(aliceSizes)-sum(bobSizes))//2\n",
    "        for a in aliceSizes:\n",
    "            if a-tmp in bobSizes:\n",
    "                return [a,a-tmp]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        dif = sum(aliceSizes) - sum(bobSizes)\n",
    "        alice_target = [i+dif/2 for i in bobSizes]\n",
    "        for alice in aliceSizes:\n",
    "            if alice in alice_target:\n",
    "                return [alice, alice - dif//2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        _ = (sum(aliceSizes) - sum(bobSizes)) // 2\n",
    "        res = []\n",
    "        for i in aliceSizes:\n",
    "            if i - _ in bobSizes:\n",
    "                res.append(i)\n",
    "                res.append(i - _)\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        看的别人的题解:用的二分查找\n",
    "        \"\"\"\n",
    "        ans = [0]*2\n",
    "        suma, sumb = 0, 0\n",
    "\n",
    "        for i in range(len(aliceSizes)):\n",
    "            suma = suma + aliceSizes[i]\n",
    "        \n",
    "        for j in range(len(bobSizes)):\n",
    "            sumb = sumb + bobSizes[j]\n",
    "\n",
    "        aliceSizes = sorted(aliceSizes)\n",
    "        bobSizes = sorted(bobSizes)\n",
    "\n",
    "        half = suma - (suma + sumb) // 2\n",
    "        i, j = 0, 0\n",
    "        while i < len(aliceSizes) and j < len(bobSizes):\n",
    "            if aliceSizes[i] - bobSizes[j] == half:\n",
    "                ans[0] = aliceSizes[i]\n",
    "                ans[1] = bobSizes[j]\n",
    "                break\n",
    "            elif aliceSizes[i] - bobSizes[j] > half:\n",
    "                j = j + 1 \n",
    "            elif aliceSizes[i] - bobSizes[j] < half:\n",
    "                i = i + 1\n",
    "\n",
    "        return ans  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sumA, sumB = sum(aliceSizes), sum(bobSizes)\n",
    "        delta = (sumA - sumB) // 2\n",
    "        res = []\n",
    "        for i in aliceSizes:\n",
    "            if i - delta in bobSizes:\n",
    "                res.append(i)\n",
    "                res.append(i - delta)\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## 思路：1）先计算糖果总数的差值；\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        aliceSizes.sort(reverse=True)\n",
    "        bobSizes.sort(reverse=True)\n",
    "        sub = sum(aliceSizes) - sum(bobSizes)\n",
    "        #print(sub)\n",
    "        flg = 0\n",
    "        if sub < 0 : \n",
    "            aliceSizes, bobSizes = bobSizes, aliceSizes\n",
    "            sub = -sub\n",
    "            flg = 1\n",
    "        sub //= 2\n",
    "        i,j = 0,0\n",
    "        while i < len(aliceSizes) and j < len(bobSizes):\n",
    "            cur = aliceSizes[i] - bobSizes[j]\n",
    "            if cur == sub: \n",
    "                if not flg: return [aliceSizes[i], bobSizes[j]]\n",
    "                else: return[bobSizes[j],aliceSizes[i]]\n",
    "            elif cur < sub:\n",
    "                j += 1\n",
    "            else: i += 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## 思路：1）先计算糖果总数的差值；2）从大到小排序；3）元素做差，直到找到两个元素的差值刚好等于总数差值的一半\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "\n",
    "        aliceSizes.sort(reverse=True)\n",
    "        bobSizes.sort(reverse=True)\n",
    "        sub = sum(aliceSizes) - sum(bobSizes)\n",
    "        #print(sub)\n",
    "        #flg = 0\n",
    "        #if sub < 0 : \n",
    "            #aliceSizes, bobSizes = bobSizes, aliceSizes\n",
    "            #sub = -sub\n",
    "            #flg = 1\n",
    "        sub //= 2\n",
    "        i,j = 0,0\n",
    "        while i < len(aliceSizes) and j < len(bobSizes):\n",
    "            cur = aliceSizes[i] - bobSizes[j]\n",
    "            if cur == sub: \n",
    "                return [aliceSizes[i],bobSizes[j]]\n",
    "                #if not flg: return [aliceSizes[i], bobSizes[j]]\n",
    "                #else: return[bobSizes[j],aliceSizes[i]]\n",
    "            elif cur < sub:\n",
    "                j += 1\n",
    "            else: i += 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        suma=sum(aliceSizes)\n",
    "        sumb=sum(bobSizes)\n",
    "        if suma==sumb:\n",
    "            return [0,0]\n",
    "        fair=(suma+sumb)//2\n",
    "        tempsum=max(suma,sumb)\n",
    "        for i in aliceSizes if suma>fair else bobSizes:\n",
    "            if fair-tempsum+i in (aliceSizes if suma<fair else bobSizes):\n",
    "                return [i,fair-tempsum+i] if tempsum==suma else [fair-tempsum+i,i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        def binary_search(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif nums[mid] > target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    return mid\n",
    "            return -1\n",
    "        def help(a, b):\n",
    "            sa = sum(a)\n",
    "            sb = sum(b)\n",
    "            a.sort()\n",
    "            for i in b:\n",
    "                k = binary_search(a, ((sa - sb) + 2 * i) / 2)\n",
    "                if k >= 0:\n",
    "                    return a[k], i\n",
    "        if len(aliceSizes) > len(bobSizes):\n",
    "            A, B = help(aliceSizes, bobSizes)\n",
    "            return [A, B]\n",
    "        else:\n",
    "            A, B = help(bobSizes, aliceSizes)\n",
    "            return [B, A]\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        s1 = sum(aliceSizes)\n",
    "        s2 = sum(bobSizes)\n",
    "        aliceSizes.sort()\n",
    "        bobSizes.sort()\n",
    "        avg = (s1 + s2) / 2\n",
    "        for i in aliceSizes:\n",
    "            # for j in bobSizes:\n",
    "            #     if s1 - i + j == avg:\n",
    "            #         return (i, j)\n",
    "            start = 0\n",
    "            end = len(bobSizes) - 1\n",
    "            mid = (start + end) >> 1\n",
    "            while start <= end:\n",
    "                s = s1 - i + bobSizes[mid]\n",
    "                if s == avg:\n",
    "                    return (i, bobSizes[mid])\n",
    "                elif s < avg:\n",
    "                    start = mid + 1\n",
    "                else:\n",
    "                    end = mid - 1\n",
    "                mid = (start + end) >> 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\r\n",
    "        a=sum(aliceSizes)\r\n",
    "        b=sum(bobSizes)\r\n",
    "        for ali in aliceSizes:\r\n",
    "            bob=-(a-2*ali-b)//2\r\n",
    "            if bob in bobSizes:\r\n",
    "                return [ali,bob]\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:  \n",
    "        tmp = (sum(aliceSizes) - sum(bobSizes)) >> 1\n",
    "        for a in aliceSizes:\n",
    "            if a - tmp in bobSizes: return [a, a - tmp]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        target = (sum(aliceSizes)-sum(bobSizes))//2\n",
    "        b_set =set(bobSizes)\n",
    "        for a in aliceSizes:\n",
    "            if a - target in b_set:\n",
    "                return [a, a - target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        tmp = (sum(aliceSizes)-sum(bobSizes))>>1\n",
    "        for a in aliceSizes:\n",
    "            if a-tmp in bobSizes:\n",
    "                return [a,a-tmp]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## 思路：1）先计算糖果总数的差值；2）从大到小排序；3）元素做差，直到找到两个元素的差值刚好等于总数差值的一半；空间复杂度，不算排序的话，O(1)；时间复杂度，不算排序的话，O(n)，因为最多只要遍历两个列表。\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        ## 归并排序\n",
    "        def merge(left,right):\n",
    "            res = []\n",
    "            i, j = 0, 0\n",
    "            while i < len(left) and j < len(right):\n",
    "                if left[i] >= right[j]:\n",
    "                    res.append(left[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(right[j])\n",
    "                    j += 1\n",
    "            if i == len(left): res += right[j:]\n",
    "            else: res += left[i:]\n",
    "            return res\n",
    "        def merge_sort(lst):\n",
    "            if len(lst) <= 1: return lst\n",
    "            mid = len(lst) // 2\n",
    "            l = merge_sort(lst[:mid])\n",
    "            r = merge_sort(lst[mid:])\n",
    "            return merge(l,r)\n",
    "\n",
    "        aliceSizes.sort(reverse=True)\n",
    "        #aliceSizes = merge_sort(aliceSizes)\n",
    "        #print(aliceSizes)\n",
    "        bobSizes.sort(reverse=True)\n",
    "        #bobSizes = merge_sort(bobSizes)\n",
    "        #print(bobSizes)\n",
    "        sub = sum(aliceSizes) - sum(bobSizes)\n",
    "        sub //= 2\n",
    "        i,j = 0,0\n",
    "        while i < len(aliceSizes) and j < len(bobSizes):\n",
    "            cur = aliceSizes[i] - bobSizes[j]\n",
    "            if cur == sub: \n",
    "                return [aliceSizes[i],bobSizes[j]]\n",
    "            elif cur < sub:\n",
    "                j += 1\n",
    "            else: i += 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        list1 = aliceSizes + bobSizes\n",
    "        num = sum(list1)\n",
    "        num1 = sum(aliceSizes)\n",
    "        tmp = 0\n",
    "        for i in range(len(aliceSizes)):\n",
    "            tmp = num/2 - (num1 - aliceSizes[i] ) # 可替换的bobSize[j]元素\n",
    "            if tmp in bobSizes:\n",
    "                return [aliceSizes[i],tmp]\n",
    "\n",
    "        # for i in range(len(aliceSizes)):\n",
    "        #     for j in range(len(bobSizes)):\n",
    "        #         if aliceSizes[i] != bobSizes[j]:\n",
    "        #             aliceSizes[i] , bobSizes[j] = bobSizes[j] , aliceSizes[i]\n",
    "        #             if sum(aliceSizes) == sum(bobSizes):\n",
    "        #                 return [bobSizes[j],aliceSizes[i]]\n",
    "        #             aliceSizes[i] , bobSizes[j] = bobSizes[j] , aliceSizes[i]\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sum_a = sum(aliceSizes)\n",
    "        bobs = set(bobSizes)\n",
    "        t = (sum(aliceSizes) + sum(bobSizes)) // 2\n",
    "        for num in aliceSizes:\n",
    "            tmp = t - sum_a + num\n",
    "            if tmp in bobs:\n",
    "                return [num, tmp]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\r\n",
    "        diff=sum(bobSizes)-sum(aliceSizes)\r\n",
    "        bobSizes=Counter(bobSizes)\r\n",
    "        \r\n",
    "        for ali in aliceSizes:\r\n",
    "            bob=ali+diff//2\r\n",
    "            if bob in bobSizes:\r\n",
    "                return [ali,bob]\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        alice, bob = sum(aliceSizes), sum(bobSizes)\n",
    "        diff = (alice - bob)/2\n",
    "        a = Counter(aliceSizes)\n",
    "        b = list(a.keys())\n",
    "        for bobSize in bobSizes:\n",
    "            if (bobSize + diff) in b:\n",
    "                return[bobSize+diff, bobSize]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        f=0\n",
    "        # if len(aliceSizes)<len(bobSizes):\n",
    "        #     aliceSizes,bobSizes=bobSizes,aliceSizes\n",
    "        #     f=1\n",
    "\n",
    "        aS=sum(aliceSizes)\n",
    "        bS=sum(bobSizes)\n",
    "        av=aS-bS\n",
    "        dv=int(av/2)\n",
    "        mb={}\n",
    "        for b in bobSizes:\n",
    "            mb[b]=1\n",
    "        for a in aliceSizes:\n",
    "            if mb.get(a-dv,0)==1:\n",
    "                if f==1:\n",
    "                    return [a-dv,a]\n",
    "                return [a,a-dv]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        suma, sumb, setb = sum(aliceSizes), sum(bobSizes), set(bobSizes)\n",
    "        target = (suma + sumb) // 2\n",
    "        for a in aliceSizes:\n",
    "            expect_b = target - (suma - a)\n",
    "            if expect_b in setb:\n",
    "                return [a, expect_b]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        # if len(aliceSizes)<len(bobSizes):\n",
    "        #     t=bobSizes\n",
    "        #     bobSizes=aliceSizes\n",
    "        #     aliceSizes=t\n",
    "        aS=sum(aliceSizes)\n",
    "        bS=sum(bobSizes)\n",
    "        av=aS-bS\n",
    "        dv=int(av/2)\n",
    "        mb={}\n",
    "        for b in bobSizes:\n",
    "            mb[b]=1\n",
    "        for a in aliceSizes:\n",
    "            if mb.get(a-dv,0)==1:\n",
    "                return [a,a-dv]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        diff = sum(B) - sum(A)\n",
    "        dic = collections.Counter(A)\n",
    "        for b in B:\n",
    "            if b - diff // 2 in dic:\n",
    "                return [b - diff // 2, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        a = sum(aliceSizes)\n",
    "        b = sum(bobSizes)\n",
    "        change = (b-a)//2\n",
    "        aliceSizes_set = set(aliceSizes)\n",
    "        for bobSize in bobSizes:\n",
    "            if bobSize-change in aliceSizes_set:\n",
    "                return bobSize-change,bobSize"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        aa,bb,setb = sum(a),sum(b), set(b)\n",
    "        t = (aa + bb) // 2\n",
    "        for i in a:\n",
    "            expectb = t - (aa - i)\n",
    "            if expectb in setb:\n",
    "                return [i, expectb]\n",
    "        return [] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        alice_sum, bob_sum = sum(aliceSizes), sum(bobSizes)\n",
    "        equal = (alice_sum+bob_sum)//2\n",
    "        pair_subtract = abs(equal - alice_sum)\n",
    "        bobset = set(bobSizes)\n",
    "        for num in aliceSizes:\n",
    "            if equal-(alice_sum-num) in bobset:\n",
    "                return [num, equal-(alice_sum-num)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sum_a = sum(aliceSizes)\n",
    "        sum_b = sum(bobSizes)\n",
    "        rec = set(bobSizes)\n",
    "        for x in aliceSizes:\n",
    "            y = x - (sum_a - sum_b)//2\n",
    "            if y in rec:\n",
    "                return [x, y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        #法1 超出时间限制\n",
    "        # res = []\n",
    "        # for i in range(len(bobSizes)):\n",
    "        #     for j in range(len(aliceSizes)):\n",
    "        #         newAli = sum(aliceSizes) + bobSizes[i] - aliceSizes[j]\n",
    "        #         newBob = sum(bobSizes) - bobSizes[i] + aliceSizes[j]\n",
    "        #         # print(newAli)\n",
    "        #         # print(newBob)\n",
    "        #         if newAli == newBob:\n",
    "        #             res.append(aliceSizes[j])\n",
    "        #             res.append(bobSizes[i])\n",
    "        #             return res\n",
    "        \n",
    "        # 法2 \n",
    "        # 挑选A和B应该满足a_sum-A+B = b_sum-B+A\n",
    "        # 整理得A-B = (a_sum-b_sum)//2 = target\n",
    "        # 在Alice对应的列表中挑选元素A，查找B=A-target是否位于Bob对应的哈希表中\n",
    "        res =[]\n",
    "        target = (sum(aliceSizes) -sum(bobSizes)) // 2\n",
    "        # print(target)\n",
    "        for a in aliceSizes:\n",
    "            if a - target in set(bobSizes):\n",
    "                return [a, a - target]\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        f=0\n",
    "        if len(aliceSizes)<len(bobSizes):\n",
    "            aliceSizes,bobSizes=bobSizes,aliceSizes\n",
    "            f=1\n",
    "\n",
    "        aS=sum(aliceSizes)\n",
    "        bS=sum(bobSizes)\n",
    "        av=aS-bS\n",
    "        dv=int(av/2)\n",
    "        mb={}\n",
    "        for b in bobSizes:\n",
    "            mb[b]=1\n",
    "        for a in aliceSizes:\n",
    "            if mb.get(a-dv,0)==1:\n",
    "                if f==1:\n",
    "                    return [a-dv,a]\n",
    "                return [a,a-dv]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sum_A, sum_B, set_B = sum(aliceSizes), sum(bobSizes), set(bobSizes)\n",
    "        target = (sum_A + sum_B) // 2\n",
    "        for a in aliceSizes:\n",
    "            expect_b = target - (sum_A - a)\n",
    "            if expect_b in set_B:\n",
    "                return [a, expect_b]\n",
    "        return []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        i = 0\n",
    "        ans = []\n",
    "        aliceSizes.sort()\n",
    "        bobSizes.sort()\n",
    "        sum_a = sum(aliceSizes)\n",
    "        bobs = set(bobSizes)\n",
    "        t = (sum(aliceSizes) + sum(bobSizes)) // 2\n",
    "        while i < len(aliceSizes):\n",
    "            tmp = t - sum_a + aliceSizes[i]\n",
    "            if tmp in bobs:\n",
    "                ans.append(aliceSizes[i])\n",
    "                ans.append(tmp)\n",
    "                return ans\n",
    "            i = i + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "    \n",
    "        sa, sb = sum(aliceSizes), sum(bobSizes)\n",
    "        \n",
    "        diff = (sa - sb) // 2\n",
    "       \n",
    "        s = set(aliceSizes)\n",
    "        \n",
    "       \n",
    "        for i in bobSizes:\n",
    "             if  i + diff in s:\n",
    "                  return [i + diff, i]\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sumA, sumB = sum(aliceSizes), sum(bobSizes)\n",
    "        delta = (sumA - sumB) // 2\n",
    "        rec = set(aliceSizes)\n",
    "        ans = None\n",
    "        for y in bobSizes:\n",
    "            x = y + delta\n",
    "            if x in rec:\n",
    "                ans = [x, y]\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        suma=sum(aliceSizes)\n",
    "        sumb=sum(bobSizes)\n",
    "        diff=(suma-sumb)//2\n",
    "        rec=set(aliceSizes)\n",
    "        ans=None\n",
    "        for y in bobSizes:\n",
    "            x=y+diff\n",
    "            if x in rec:\n",
    "                ans=[x,y]\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        s1 = sum(aliceSizes)\n",
    "        s2 = sum(bobSizes)\n",
    "        s = set(aliceSizes)\n",
    "        avg = (s1 + s2) / 2\n",
    "        for j in bobSizes:\n",
    "            delta = int(avg + j - s2)\n",
    "            if delta in s:\n",
    "                return (delta, j)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sumA, sumB = sum(aliceSizes), sum(bobSizes)\n",
    "        delta = (sumA - sumB) // 2\n",
    "        rec = set(aliceSizes)\n",
    "        ans = None\n",
    "        for y in bobSizes:\n",
    "            x = y + delta\n",
    "            if x in rec:\n",
    "                ans = [x, y]\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        k, b = (sum(aliceSizes) - sum(bobSizes)) // 2, set(bobSizes)\n",
    "        for v in aliceSizes:\n",
    "            if v - k in bobSizes: return [v, v - k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        # 哈希表\n",
    "        # 由题解公式得\n",
    "        #将Alice的数存入哈希表，遍历bob,在Alice中查询找到符合条件的数\n",
    "        sumA, sumB = sum(aliceSizes), sum(bobSizes)\n",
    "        delta = (sumA - sumB) // 2\n",
    "        rec = set(aliceSizes) # 将Alice的数存入哈希表，哈希表可以是字典或者集合\n",
    "        ans = None\n",
    "        for y in bobSizes:\n",
    "            x = y + delta\n",
    "            if x in rec:\n",
    "                ans = [x, y]\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## 思路：1）先计算糖果总数的差值；2）从大到小排序；3）元素做差，直到找到两个元素的差值刚好等于总数差值的一半；空间复杂度，不算排序的话，O(1)；时间复杂度，不算排序的话，O(n)，因为最多只要遍历两个列表。\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        ## 归并排序\n",
    "        def merge(left,right):\n",
    "            res = []\n",
    "            i, j = 0, 0\n",
    "            while i < len(left) and j < len(right):\n",
    "                if left[i] >= right[j]:\n",
    "                    res.append(left[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(right[j])\n",
    "                    j += 1\n",
    "            if i == len(left): res += right[j:]\n",
    "            else: res += left[i:]\n",
    "            return res\n",
    "        def merge_sort(lst):\n",
    "            if len(lst) <= 1: return lst\n",
    "            mid = len(lst) // 2\n",
    "            l = merge_sort(lst[:mid])\n",
    "            r = merge_sort(lst[mid:])\n",
    "            return merge(l,r)\n",
    "\n",
    "        #aliceSizes.sort(reverse=True)\n",
    "        aliceSizes = merge_sort(aliceSizes)\n",
    "        #print(aliceSizes)\n",
    "        #bobSizes.sort(reverse=True)\n",
    "        bobSizes = merge_sort(bobSizes)\n",
    "        #print(bobSizes)\n",
    "        sub = sum(aliceSizes) - sum(bobSizes)\n",
    "        sub //= 2\n",
    "        i,j = 0,0\n",
    "        while i < len(aliceSizes) and j < len(bobSizes):\n",
    "            cur = aliceSizes[i] - bobSizes[j]\n",
    "            if cur == sub: \n",
    "                return [aliceSizes[i],bobSizes[j]]\n",
    "            elif cur < sub:\n",
    "                j += 1\n",
    "            else: i += 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        totalA, totalB = sum(aliceSizes), sum(bobSizes)\n",
    "        diff = (totalA - totalB) // 2\n",
    "        hashA, hashB = Counter(aliceSizes), Counter(bobSizes)\n",
    "        for i in hashA:\n",
    "            if i - diff in hashB:\n",
    "                return [i, i-diff]\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        sum_A = sum(A)\n",
    "        sum_B = sum(B)\n",
    "        delta = (sum_A - sum_B) // 2\n",
    "        total = set(A)\n",
    "\n",
    "        for i in B:\n",
    "            j = i + delta\n",
    "            if j in total:\n",
    "                return [j, i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        # for i in range(len(aliceSizes)):\n",
    "        #     temp_alice = aliceSizes.copy()\n",
    "        #     temp_alice.pop(i)\n",
    "\n",
    "        #     for j in range(len(bobSizes)):\n",
    "        #         temp_bob = bobSizes.copy()\n",
    "        #         temp_bob.pop(j)\n",
    "        #         if sum(temp_alice) + bobSizes[j]  == sum(temp_bob)+aliceSizes[i]                :\n",
    "        #             return [aliceSizes[i], bobSizes[j]]\n",
    "\n",
    "        sumA, sumB = sum(aliceSizes), sum(bobSizes)\n",
    "        delta = (sumA - sumB) // 2\n",
    "        rec = set(aliceSizes)\n",
    "        ans = None\n",
    "        for y in bobSizes:\n",
    "            x = y + delta\n",
    "            if x in rec:\n",
    "                ans = [x, y]\n",
    "                break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        s1=sum(aliceSizes)\n",
    "        s2=sum(bobSizes)\n",
    "        d=(s1-s2)//2\n",
    "        s=set(aliceSizes)\n",
    "        res=[]\n",
    "        for i in range(len(bobSizes)):\n",
    "            t=bobSizes[i]+d\n",
    "            if t in s:\n",
    "                res.append(t)\n",
    "                res.append(bobSizes[i])\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        alice_sum = sum(aliceSizes)\n",
    "        bob_sum = sum(bobSizes)\n",
    "        diff = (bob_sum - alice_sum) // 2\n",
    "\n",
    "        required = set()\n",
    "        for i in aliceSizes:\n",
    "            required.add(i + diff)\n",
    "        print(required)\n",
    "        for i in bobSizes:\n",
    "            if i in required:\n",
    "                return [i-diff, i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        dif = (sum(aliceSizes) + sum(bobSizes)) // 2 - sum(aliceSizes)\n",
    "        # for i in range(len(aliceSizes)):\n",
    "        #     for j in range(len(bobSizes)):\n",
    "        #         if bobSizes[j] - aliceSizes[i] == dif:\n",
    "        #             ans.append(aliceSizes[i])\n",
    "        #             ans.append(bobSizes[j])\n",
    "        #             return ans\n",
    "\n",
    "        rec = set(aliceSizes)\n",
    "        for i in bobSizes:\n",
    "            if i - dif in rec:\n",
    "                ans.append(i-dif)\n",
    "                ans.append(i)\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        a_sum = sum(aliceSizes)\n",
    "        b_sum = sum(bobSizes)\n",
    "        gap = a_sum - b_sum\n",
    "        table_b = set(bobSizes)\n",
    "        for candy in aliceSizes:\n",
    "            if  (candy - gap//2) in table_b:\n",
    "                return [candy, candy - gap//2] \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sum_a, sum_b = 0, 0\n",
    "        isNeg = False\n",
    "        a2cnt, b2cnt = {}, {}\n",
    "        for ai in aliceSizes:\n",
    "            if ai not in a2cnt:\n",
    "                a2cnt[ai] = 1\n",
    "            sum_a += ai\n",
    "        for bi in bobSizes:\n",
    "            if bi not in b2cnt:\n",
    "                b2cnt[bi] = 1\n",
    "            sum_b += bi\n",
    "        diff = sum_a - sum_b >> 1\n",
    "        if diff < 0:\n",
    "            aliceSizes, bobSizes = bobSizes, aliceSizes\n",
    "            a2cnt, b2cnt = b2cnt, a2cnt\n",
    "            diff = -diff \n",
    "            isNeg = True\n",
    "        for ai in a2cnt.keys():\n",
    "            if ai - diff in b2cnt:\n",
    "                if isNeg: \n",
    "                    return [ai - diff, ai]\n",
    "                else:\n",
    "                    return [ai, ai - diff]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sumA, sumB = sum(aliceSizes), sum(bobSizes)\n",
    "        delta = (sumA - sumB) // 2\n",
    "        rec = set(aliceSizes)\n",
    "        ans = None\n",
    "        for y in bobSizes:\n",
    "            x = y + delta\n",
    "            if x in rec:\n",
    "                return [x, y]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def fairCandySwap(self, aliceSizes, bobSizes):\n",
    "        \"\"\"\n",
    "        :type aliceSizes: List[int]\n",
    "        :type bobSizes: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        # 计算总和并创建字典\n",
    "        diff = (sum(aliceSizes) - sum(bobSizes))//2\n",
    "        bob_dict = {size: i for i, size in enumerate(bobSizes)}\n",
    "        \n",
    "        # 遍历爱丽丝的糖果大小\n",
    "        for i in set(aliceSizes):\n",
    "            # 计算目标差值\n",
    "            target = i-diff\n",
    "            # 检查目标是否存在于字典中\n",
    "            if target in bob_dict:\n",
    "                return [i, target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:\n",
    "        temp1=sum(A)\n",
    "        temp2=sum(B)\n",
    "        chazhi=(temp1-temp2)//2\n",
    "        hasb=collections.defaultdict(list)\n",
    "        for i in B: hasb[i]=[1]\n",
    "        for i in A: \n",
    "            if hasb[i-chazhi]: \n",
    "                return [i,i-chazhi]\n",
    "\n",
    "\n",
    "        '''\n",
    "        chazhi=int((sum(A)-sum(B))/2)\n",
    "        A.sort()\n",
    "        B.sort()\n",
    "        heada,headb=0,0\n",
    "        taila,tailb=len(A),len(B)\n",
    "        while headb<tailb and heada<taila:\n",
    "            temp=A[heada]-B[headb]\n",
    "            if temp>chazhi:\n",
    "                headb+=1\n",
    "            elif temp<chazhi:\n",
    "                heada+=1\n",
    "            else: return [A[heada],B[headb]]\n",
    "        return False\n",
    "        '''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ## 思路：1）先计算糖果总数的差值；2）从大到小排序；3）元素做差，直到找到两个元素的差值刚好等于总数差值的一半；空间复杂度，不算排序的话，O(1)；时间复杂度，不算排序的话，O(n)，因为最多只要遍历两个列表。\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        ## 归并排序\n",
    "        def merge(left,right):\n",
    "            res = []\n",
    "            i, j = 0, 0\n",
    "            while i < len(left) and j < len(right):\n",
    "                if left[i] >= right[j]:\n",
    "                    res.append(left[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    res.append(right[j])\n",
    "                    j += 1\n",
    "            if i == len(left): res += right[j:]\n",
    "            else: res += left[i:]\n",
    "            return res\n",
    "        def merge_sort(lst):\n",
    "            if len(lst) <= 1: return lst\n",
    "            mid = len(lst) // 2\n",
    "            l = merge_sort(lst[:mid])\n",
    "            r = merge_sort(lst[mid:])\n",
    "            return merge(l,r)\n",
    "\n",
    "        #aliceSizes.sort(reverse=True)\n",
    "        aliceSizes = merge_sort(aliceSizes)\n",
    "        print(aliceSizes)\n",
    "        #bobSizes.sort(reverse=True)\n",
    "        bobSizes = merge_sort(bobSizes)\n",
    "        print(bobSizes)\n",
    "        sub = sum(aliceSizes) - sum(bobSizes)\n",
    "        sub //= 2\n",
    "        i,j = 0,0\n",
    "        while i < len(aliceSizes) and j < len(bobSizes):\n",
    "            cur = aliceSizes[i] - bobSizes[j]\n",
    "            if cur == sub: \n",
    "                return [aliceSizes[i],bobSizes[j]]\n",
    "            elif cur < sub:\n",
    "                j += 1\n",
    "            else: i += 1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, a: List[int], b: List[int]) -> List[int]:\n",
    "        s1, s2 = sum(a), sum(b)\n",
    "        s = (s1 + s2) // 2\n",
    "        h1, h2 = set(a), set(b)\n",
    "        if s > s1:\n",
    "            for x in a:\n",
    "                d = s - s1 + x\n",
    "                if d in h2:\n",
    "                    return [x, d]\n",
    "        if s > s2:\n",
    "            for x in b:\n",
    "                d = s - s2 + x\n",
    "                if d in h1:\n",
    "                    return [d, x]\n",
    "        return [-1, -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        a, b = sum(aliceSizes), sum(bobSizes)\n",
    "        avg = (a + b) // 2\n",
    "        aliceSizes, bobSizes = set(aliceSizes), set(bobSizes)\n",
    "        for x in aliceSizes:\n",
    "            y = avg - a + x\n",
    "            if y in bobSizes:\n",
    "                return [x, y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        delta = sum(bobSizes) - sum(aliceSizes)\n",
    "        sa = set(aliceSizes)\n",
    "        sb = set(bobSizes)\n",
    "        for a in sa:\n",
    "            b = a + delta // 2\n",
    "            if b in sb:\n",
    "                return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sub = (sum(aliceSizes) - sum(bobSizes)) // 2\n",
    "        A = set(aliceSizes)\n",
    "        B = set(bobSizes)\n",
    "        for i in A:\n",
    "            if i - sub in B:\n",
    "                return [i, i - sub]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "                result = []\n",
    "                sum_alice = sum(aliceSizes)\n",
    "                sum_bob = sum(bobSizes)\n",
    "\n",
    "                hash_map_alice = {}\n",
    "                hash_map_bob = {}\n",
    "                for a in aliceSizes:\n",
    "                        hash_map_alice[a] = sum_alice - 2 *a\n",
    "                for b in bobSizes:\n",
    "                        hash_map_bob[sum_bob - 2*b] = b\n",
    "\n",
    "\n",
    "                for alice_key, alice_value in hash_map_alice.items():\n",
    "                        if alice_value in hash_map_bob.keys():\n",
    "                                result.append(alice_key)\n",
    "                                result.append(hash_map_bob[alice_value])\n",
    "                                return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        totalA, totalB = sum(aliceSizes), sum(bobSizes)\n",
    "        diff = (totalA - totalB) // 2\n",
    "        hashA, hashB = set(aliceSizes), set(bobSizes)\n",
    "        for i in hashA:\n",
    "            if i - diff in hashB:\n",
    "                return [i, i-diff]\n",
    "        return []\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sub = (sum(aliceSizes) + sum(bobSizes)) // 2 - sum(aliceSizes)\n",
    "        for i in set(aliceSizes):\n",
    "            if i + sub in set(bobSizes):\n",
    "                return [i, i + sub]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        # aliceSizes.sort()\n",
    "        # bobSizes.sort()\n",
    "        # # 定义双指针 超时\n",
    "        # n,m = 0,0\n",
    "        # # 如果交换后两边不等就继续循环\n",
    "        # while sum(aliceSizes)-aliceSizes[n]+bobSizes[m] != sum(bobSizes)-bobSizes[m]+aliceSizes[n]:\n",
    "        #     # 交换后左边大了就左指针加1,不然就右指针加1\n",
    "        #     if sum(aliceSizes)-aliceSizes[n]+bobSizes[m] < sum(bobSizes)-bobSizes[m]+aliceSizes[n]:\n",
    "        #         m += 1\n",
    "        #     else:\n",
    "        #         n += 1\n",
    "        # return [aliceSizes[n],bobSizes[m]]\n",
    "\n",
    "        # 先求出两人交换后应有的糖果数\n",
    "        s = (sum(aliceSizes)+sum(bobSizes)) * 0.5\n",
    "        # 计算aliceSizes的和和应有数值的差\n",
    "        d = sum(aliceSizes) - s\n",
    "        # 看一下两个列表中都有哪些数\n",
    "        a,b = set(aliceSizes),set(bobSizes)\n",
    "        # 如果a中某个数字与b中某个数字的差值的等于aliceSizes的和和应有数值的差那么就该交换这两个数字\n",
    "        for i in a:\n",
    "            if i - d in b:\n",
    "                return [i,i-d]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        sum_a, sum_b = sum(aliceSizes), sum(bobSizes)\n",
    "        diff = (sum_a - sum_b) // 2\n",
    "        A, B = set(aliceSizes), set(bobSizes)\n",
    "        for na in A:\n",
    "            if (na - diff) in B:\n",
    "                return [na, na-diff]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        differ = (sum(aliceSizes) - sum(bobSizes))/2\n",
    "        calice = dict(Counter(aliceSizes))\n",
    "        cbob = dict(Counter(bobSizes))\n",
    "        for k, v in calice.items():\n",
    "            if cbob.get(k - differ) != None:\n",
    "                return [k, k - differ]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "        nums = sum(aliceSizes + bobSizes) // 2\n",
    "        n1 = sum(aliceSizes)\n",
    "        for i in set(aliceSizes):\n",
    "            if nums - (n1-i) in set(bobSizes):\n",
    "                return [i,nums-(n1-i)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:\n",
    "    \n",
    "        sa, sb = sum(aliceSizes), sum(bobSizes)\n",
    "        \n",
    "        diff = (sa - sb) // 2\n",
    "       \n",
    "        s1, s2 = set(aliceSizes), set(bobSizes)\n",
    "        \n",
    "        \n",
    "       \n",
    "        for i in s2:\n",
    "             if  i + diff in s1:\n",
    "                  return [i + diff, i]\n",
    "       "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
